package com.atguigu.pa;

import java.util.Arrays;

public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {3,1,5,8,4,7,6,2};
        mergeSort(arr);
        System.out.println(Arrays.toString(arr));
    }

    private static void mergeSort(int[] arr) {
        mergeSort(arr,0,arr.length-1);
    }

    private static void mergeSort(int[] arr, int start, int end) {
        //递归的终止条件：当只剩一个元素(start==end)时，就没有必要再继续拆分了
        if(start>=end){
            return;
        }

        int mid = (start+end)/2;
        mergeSort(arr,start,mid);
        mergeSort(arr,mid+1,end);
        merge(arr,start,mid,end);
    }

    private static void merge(int[] arr, int start, int mid, int end) {
        int[] tempArr = new int[end-start+1];
        int i = start ;
        int j = mid+1;
        int k = 0 ; //k用来记录当前tempArr的索引位置
        while(i<=mid && j<=end) {
            tempArr[k++] = (arr[i] < arr[j]) ? arr[i++] : arr[j++];
        }
        while(i<=mid){
            tempArr[k++]=arr[i++];
        }
        while(j<=end){
            tempArr[k++]=arr[j++];
        }
        System.arraycopy(tempArr,0,arr,start,tempArr.length);
    }
}
